/*
 * gbm.cpp
 *
 *  Created on: Mar 24, 2011
 *      Author: cookiemouse
 */

//ŠbTIList€€¥HnumberofnodeÀxŠsunique item­ÓŒÆ
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <iomanip>
#include <string>
#include <stack>
#include <vector>
#include <sstream>
#include <time.h>
//#include <conio.h>

#include <map>
#include "mining.h"


inline string int2string(int n)
{
	stringstream ss;
	string temp;
	ss << n;
	ss >> temp;
	return temp;
}

inline int string2int(string s)
{
	istringstream strin(s);
	int i;
	strin >> i;
	return i;
}


// ListNode in the TIList

//	ListNode in the TIList


TIList::TIList()
{
    numberofnode = 0;
	List.clear();
}

TIList::~TIList()
{
    numberofnode = 0;
	List.~vector();
}

void TIList::insert(TIListNode NewNode)
{
	List.push_back(NewNode);

	if (List.size() == 1)
		numberofnode++;
	else if ((List.size() > 1) && List.at(List.size()-2).TIDIndex != List.back().TIDIndex)
		numberofnode++;

}

void TIList::insert(int tidindex, int time, int cmark)
{

	TIListNode NewNode = {tidindex, time, cmark};
    List.push_back(NewNode);

	if (List.size() == 1)
		numberofnode++;
	else if ((List.size() > 1) && List.at(List.size()-2).TIDIndex != List.back().TIDIndex)
		numberofnode++;

}

void TIList::insert(TIListNode* pTIListNode)
{

	TIListNode NewNode = {pTIListNode->TIDIndex, pTIListNode->Timestamp, pTIListNode->Mark};
    List.push_back(NewNode);

	if (List.size() == 1)
		numberofnode++;
	else if ((List.size() > 1) && List.at(List.size()-2).TIDIndex != List.back().TIDIndex)
		numberofnode++;

}

void TIList::clear()
{
     List.clear();
     numberofnode = 0;
}

bool TIList::empty()
{
	return List.empty();
}

TIListNode* TIList::at(int index)
{
    return &(List.at(index));
}

TIListNode* TIList::back()
{
	return &(List.back());
}

int TIList::size()
{
    return List.size();
}

//==============================================================================




//constructor
ReferenceSpace::ReferenceSpace(int k, int MTS, int MS )
{
	length			= k;      //the max(width, height) of our 2D space
	Max_TimeSpan	= MTS;    //the maximun allowed timespan between two movement
	Min_Support		= MS;
	filename		= "M-k"+int2string(length)+"T"+int2string(Max_TimeSpan)+"S"+int2string(Min_Support)+".data";
    numberofP		= 0;
    tuplesScanned = 0;
    candidates = 0;
    candidatesarry = {0,0,0,0};

	ofstream ResultFile(filename.c_str(), ios_base::out );	              //initalize the output stream
	if (!ResultFile)
	{
		cerr << "File could not be opened" << endl;
		exit(1);
	}
	                                                                      //print the 3 paramaters in the file
	ResultFile << "The length of the reference space: " << int2string(length) << endl;
	ResultFile << "The Maximum Time Span is: " << int2string(Max_TimeSpan) << endl;
	ResultFile << "The Minimum Support Span is : " << int2string(Min_Support) << endl;
	ResultFile.close();

	space.resize(length+2);                                               //create a reference space with 2-d vector
	for(int y=0; y <= length+1; y++)
	{
		  space[y].resize(length+2);
          for(int x=0; x <= length+1; x++)
          {
				space[y][x].coordinate.x = x;
				space[y][x].coordinate.y = y;
				space[y][x].HeadPtr =new TIList();;
				space[y][x].frequent = false;
          }
	}
}

//deconstrctor
ReferenceSpace::~ReferenceSpace()
{
	delete this;
}
//checked OK
vector< TIList* > ReferenceSpace::Intersection(TIList* TIListA, TIList* TIListB)
{
    tuplesScanned = tuplesScanned + TIListA->size()+TIListB->size();
	vector< TIList* > TIListvector;                                       //save all the TIList that time span is less than maximum timespan-->{<timespan0, TIList0>,<timespan1, TIList1>....}
    TIListvector.resize(Max_TimeSpan+1);                                  //Resize the TIListvector depend on the the possible timespans

    for (int i =0; i < TIListvector.size(); i++)                          //for every possible time span
    {
        TIList* IntersectionList = new TIList();	                   //the variable wihich contians the result of intersectionList
        TIListvector[i] = IntersectionList;                               //add the empty IntersectionList into the TIListvector
	}

    int in1				= 0;
    int in2				= 0;
    int intime			= 0;
    TIListNode* index1	= (*TIListA).at(in1);
    TIListNode* index2	= (*TIListB).at(in2);

	while ( !( ( index1 == TIListA->back() ) && ( index2 == TIListB->back() ) ) )      //¯ÊÀË¬d³Ì«á€@­Ó!!¡Ašâ­Ó³£¬O³Ì«á€@­Óªº®É­Ôžõ¥X¡A®É¶¡œÆÂø«×¬Om+n
    {
		if ((index1->TIDIndex) == (index2->TIDIndex))  //TID¬Ûµ¥
		{
			intime = index2->Timestamp - index1->Timestamp;

			if ((intime <= Max_TimeSpan) && (intime >0 ) && (index2->Mark - index1->Mark == 1))//mark¬ÛŽî¬O¬°€FCHECK¬O§_³sÄò
			{
				TIListvector[intime]->insert(index2);
			}

			if (intime > 0)
			{
				if (index1 != TIListA->back())
					index1 = TIListA->at(in1++);
				else if (index2 != TIListB->back())
					index2 = TIListB->at(in2++);
			}
			else
			{
				if (index2 != TIListB->back())
					index2 = TIListB->at(in2++);
				else if (index1 != TIListA->back())
					index1 = TIListA->at(in1++);
			}
			continue;
		}

		if ((index1->TIDIndex) < (index2->TIDIndex))//TID €£µ¥
		{
			if (index1 != TIListA->back())
				index1 = TIListA->at(in1++);
			else if (index2 != TIListB->back())//WHY? BECAUSE ­nº¡š¬žõ¥Xªº±ø¥ó¡AŠpªGA€wžgšì©³€F¡A€§«áÀ³žÓ€]šSŠ³§Æ±æ€F!!šä¹ê¥i¥Hªœ±µžõ¥X
				index2 = TIListB->at(in2++);;
			continue;
		}

		if ((index1->TIDIndex) > (index2->TIDIndex))
		{

			if (index2 != TIListB->back())
				index2 = TIListB->at(in2++);
			else if (index1 != TIListA->back())//WHY? BECAUSE ­nº¡š¬žõ¥Xªº±ø¥ó¡AŠpªGB€wžgšì©³€F¡A€§«áÀ³žÓ€]šSŠ³§Æ±æ€F!!šä¹ê¥i¥Hªœ±µžõ¥X
				index1 = TIListA->at(in1++);
			continue;
		}
    }

	if ((index1->TIDIndex) == (index2->TIDIndex))						// the last 2 node will be miss checking on the above proecdure
	{
			intime = index2->Timestamp - index1->Timestamp;

			if ((intime <= Max_TimeSpan) && (intime >=0 ) && (index2->Mark - index1->Mark == 1))
			{
				TIListvector[intime]->insert(index2);
			}
	}

    return TIListvector;                                                  //return the freuqnet TIList with any possible timespan
}

void ReferenceSpace::DFS(int x, int y, TIList* InterTIList)               //interTIList ¬Ofrequent 1ªº TILIST//©Î¬O€W­Óstack ºâ¥Xªº«ePATTERN ªºTIDS
{
	this->candidates ++;
	candidatesarry[min((int)patterns.size()/2+1,3)]++;
	pattern				= ""; //?
	string pattern2print			= ""; //??

	TIList* nextList	= NULL;											  //the next point need to intersect
	vector< TIList* >	TempTIListvector;

	if (InterTIList->numberofnode >= Min_Support)                         //check if the TIlist is longer than or equal to the min support
	{
		pattern = "(" + int2string(x) + "," + int2string(y) + ")";        //transfer the pattern from int to string
		patterns.push_back( pattern );                                    //push it into the vector

		for (int printall = 1; printall<=patterns.size(); printall++)     //combine all the freuquent location as a longer pattern
		{
			pattern2print += patterns.at(printall-1);
		}
		pattern2print +="\n";                                                  //nex line
		//cout << apattern;
        numberofP++;                                                      //increase the number of pattern

		ofstream ResultFile(filename.c_str(), ios_base::out| ios::app );  //output the pattern to the output file

        if (!ResultFile)
		{
			cerr << "File could not be opened" << endl;
			exit(1);
		}

		ResultFile.clear();
		ResultFile.seekp(ios_base::end);
		ResultFile << int2string(numberofP) << "."<<int2string(InterTIList->numberofnode) <<"." <<int2string(patterns.size())<<"." <<pattern2print;            //output the the pattern numbr
		ResultFile.close();

		for (int compress  = 1; compress <= 8; compress++)                //find 8 neighbours in the reference space
		{
            switch(compress)
			{
				case 1:                                                   //¥¿€W€è
                       if ( space[y-1][x].frequent == true)               //check if the place is freuqnet place
					   {
						   nextList = space[y-1][x].HeadPtr;              //set the next list to intersect
                           TempTIListvector = Intersection(InterTIList, nextList); //returns {<timespan, TIDLis>....}List
                                                                          //return a set of intersection result with all possible timespans
  	                       for (int i = 1; i <= (TempTIListvector.size()-1); i++)
			               {                                              //for every intersection results
                               if ( TempTIListvector[i]->numberofnode >= Min_Support)
                               {	                                      //if a intersection result with a specifc timespan is frequent
                                   patterns.push_back( int2string(i) );   //add the time span to the patterns
	                               DFS(x, y-1, TempTIListvector[i]);      //use the result to further intersection
                               }
                           }
		               }
					break;
				case 2:                                                   //¥k€W€è
		               if ( space[y-1][x+1].frequent == true)             //check if the place is freuqnet place
					   {
					    	nextList = space[y-1][x+1].HeadPtr;           //set the next list to intersect
                            TempTIListvector = Intersection(InterTIList, nextList);
                                                                          //return a set of intersection result with all possible timespans
                            for (int i = 1; i <= (TempTIListvector.size()-1); i++)
						    {                                             //for every intersection results(List)
                                if ( TempTIListvector[i]->numberofnode >= Min_Support)
						        {	                                      //if a intersection result with a specifc timespan it is a frequent one
                                    patterns.push_back( int2string(i) );  //add the time span to the patterns
				      	            DFS(x+1, y-1, TempTIListvector[i]);  //use the result to further intersection
							    }
					        }
                       }
					break;
				case 3:                                                   //¥¿¥k€è
					   if ( space[y][x+1].frequent == true)               //check if the place is freuqnet place
					   {
					    	nextList = space[y][x+1].HeadPtr;             //set the next list to intersect
                            TempTIListvector = Intersection(InterTIList, nextList);
                                                                          //return a set of intersection result with all possible timespans
						    for (int i = 1; i <= (TempTIListvector.size()-1); i++)
						    {                                             //for every intersection results(List)
                                if ( TempTIListvector[i]->numberofnode >= Min_Support)
						        {	                                      //if a intersection result with a specifc timespan it is a frequent one
	                                patterns.push_back( int2string(i) );  //add the time span to the patterns
	    	                        DFS(x+1, y, TempTIListvector[i]);    //use the result to further intersection
                                }
                            }
				       }
					break;
				case 4:	                                                  //¥k€U€è
                       if ( space[y+1][x+1].frequent == true)             //check if the place is freuqnet place
					   {
					        nextList = space[y+1][x+1].HeadPtr;           //set the next list to intersect
                            TempTIListvector = Intersection(InterTIList, nextList);
                                                                          //return a set of intersection result with all possible timespans
						    for (int i = 1; i <= (TempTIListvector.size()-1); i++)
						    {                                              //for every intersection results(List)
                                if ( TempTIListvector[i]->numberofnode >= Min_Support)
						        {	                                      //if a intersection result with a specifc timespan it is a frequent one
	                                patterns.push_back( int2string(i) );  //add the time span to the patterns
									DFS(x+1, y+1, TempTIListvector[i]);  //use the result to further intersection
								}
							}
						}
					break;
				case 5:	                                                  //¥¿€U€è
					   if ( space[y+1][x].frequent == true)               //check if the place is freuqnet place
					   {
					    	nextList = space[y+1][x].HeadPtr;             //set the next list to intersect
                            TempTIListvector = Intersection(InterTIList, nextList);
                                                                          //return a set of intersection result with all possible timespans
						    for (int i = 1; i <= (TempTIListvector.size()-1); i++)
						    {                                              //for every intersection results(List)
                                if ( TempTIListvector[i]->numberofnode >= Min_Support)
						        {	                                      //if a intersection result with a specifc timespan it is a frequent one
	                                patterns.push_back( int2string(i) );  //add the time span to the patterns
									DFS(x, y+1, TempTIListvector[i]);    //use the result to further intersection
								}
							}
						}
					break;
				case 6:                                                   //¥ª€U€è
					   if ( space[y+1][x-1].frequent == true)             //check if the place is freuqnet place
					   {
					        nextList = space[y+1][x-1].HeadPtr;           //set the next list to intersect
                            TempTIListvector = Intersection(InterTIList, nextList);
                                                                          //return a set of intersection result with all possible timespans
						    for (int i = 1; i <= (TempTIListvector.size()-1); i++)
						    {                                              //for every intersection results(List)
                                if ( TempTIListvector[i]->numberofnode >= Min_Support)
						        {	                                      //if a intersection result with a specifc timespan it is a frequent one
	                                patterns.push_back( int2string(i) );  //add the time span to the patterns
									DFS(x-1, y+1, TempTIListvector[i]);   //use the result to further intersection
								}
							}
						}
					break;
				case 7:                                                   //¥¿¥ª€è
					   if ( space[y][x-1].frequent == true)               //check if the place is freuqnet place
					   {
					        nextList = space[y][x-1].HeadPtr;             //set the next list to intersect
                            TempTIListvector = Intersection(InterTIList, nextList);
                                                                          //return a set of intersection result with all possible timespans
						    for (int i = 1; i <= (TempTIListvector.size()-1); i++)
						    {                                             //for every intersection results(List)
                                if ( TempTIListvector[i]->numberofnode >= Min_Support)
						        {	                                      //if a intersection result with a specifc timespan it is a frequent one
	                                patterns.push_back( int2string(i) );  //add the time span to the patterns
									DFS(x-1, y, TempTIListvector[i]);    //use the result to further intersection
								}
							}
						}
					break;
				case 8:                                                   //¥ª€W€è
					   if ( space[y-1][x-1].frequent == true)             //check if the place is freuqnet place
					   {
					        nextList = space[y-1][x-1].HeadPtr;           //set the next list to intersect
                            TempTIListvector = Intersection(InterTIList, nextList);
                                                                          //return a set of intersection result with all possible timespans
						    for (int i = 1; i <= (TempTIListvector.size()-1); i++)
						    {                                             //for every intersection results(List)
                                if ( TempTIListvector[i]->numberofnode >= Min_Support)
						        {	                                      //if a intersection result with a specifc timespan it is a frequent one
	                                patterns.push_back( int2string(i) );  //add the time span to the patterns
									DFS(x-1, y-1, TempTIListvector[i]);   //use the result to further intersection
								}
							}
						}
					break;
			}                                                             //end of switch
		}                                                                 //end of find 8 neighbour
		if (!patterns.empty())
			patterns.pop_back();                                          //pop back the last location in the patterns
		if (!patterns.empty())
			patterns.pop_back();                                          //pop back the last timespan in the patterns
	}

}

int main(int argn, char** argvs)
{
    int k, Min_Support, Max_TimeSpan;
//	cout << "Enter the 3 paramr for the Mining process: \n";
//	cout << "Input the size of Reference Space: ";
//	cin >> k;
//	cout << "Input the Max Time Span: ";
//	cin >> Max_TimeSpan;
//	cout << "Input the Min Support: ";
//	cin >> Min_Support;
//	cout << endl;
	string inputfile = string(argvs[1]);
	k = string2int(string(argvs[2]));
	Max_TimeSpan = string2int(string(argvs[3]));
	Min_Support = string2int(string(argvs[4]));

	int cmark = 0;

	clock_t start,finish;                                                 //the start and the end of the mining process record
	double totaltime;                                                     //the total time interval
	start = clock();                                                      //start of recording the total time

	ReferenceSpace* Miningspace = new ReferenceSpace(k,Max_TimeSpan,Min_Support);
                                                                          //new Reference space(the main obejct during mining process)

	//read the data from the file Inputfile
	char ch, ch1='?';
    string content = "", contentx= "", contenty= "", contentt= "";

	//how to use the counter in space
	ifstream inSampleFile( inputfile.c_str(), ios::in);

	if (!inSampleFile)
	{
		cerr << "File could not be opened" << endl;
		exit(1);
	}


    while (inSampleFile.get(ch))
    {
		switch(ch)
		{
			case '<' :
				ch1 = '<';
				contentx = "";
				break;
			case ',' :
				if (ch1 == ',')
				{
					ch1 = '*';
					contentt = "";
				}
				else
				{
					ch1 = ',';
					contenty = "";
				}
				break;
			case '>':
				ch1 = '>';
				break;
			case '|' :
				ch1 = '|';
				Miningspace->TIDVector.push_back(content);
                break;
			case '?' :
				ch1 = '?';
				content = "";
				break;
		}

		if ((ch1 == '?') && (ch != '?'))
		{
			content +=ch;
		}

		if ((ch1 == '<') && (ch != '<'))
		{
			contentx +=ch;
		}

		if ((ch1 == ',') && (ch != ','))
		{
			contenty +=ch;
		}

		if ((ch1 == '*') && (ch != ','))
		{
			contentt +=ch;
		}

		//add node in a TIList, contentx and contty donate the specific coordinates in a reference space
		if (ch == '>')	//
		{
			Miningspace->space[string2int(contenty)][string2int(contentx)].HeadPtr->insert((Miningspace->TIDVector.size()-1), string2int(contentt), cmark);
			                                                                                //current size -1. ŽN¬O¡u¥Ø«eªº³o­ÓTID¡v why? Š]¬°ÃäÅªÃäºâªºÃö«Y

			TIList* check = Miningspace->space[string2int(contenty)][string2int(contentx)].HeadPtr;//useless!
			cmark = cmark++;
		}
    }

	inSampleFile.close();

	for ( int xc = 1; xc<=k ; xc++)
	{
		for ( int yc = 1; yc<= k; yc++)
		{
			if (Miningspace->space[yc][xc].HeadPtr->numberofnode !=0){
				Miningspace->candidatesarry[0]++;
			}
			if (Miningspace->space[yc][xc].HeadPtr->numberofnode >= Min_Support)        //check if the location is a frequent 1 space
               Miningspace->space[yc][xc].frequent = true; //­n¥ýµ¹­È¡AdfsùØ€~¯à¬Ý±o¥XžÓ€£žÓš«€U¥h
		}
	}

                                                                          //Call DFS to Mine the pattern
	for (  int xc = 1; xc<=k ; xc++)
	{
		for (  int yc = 1; yc<= k; yc++)
		{
			if (Miningspace->space[yc][xc].frequent == true){              //check if the location is a frequent 1 space
               Miningspace->DFS(xc,yc,Miningspace->space[yc][xc].HeadPtr);

            }
		}
	}

	ofstream ResultFile(Miningspace->filename.c_str(), ios_base::out| ios::app );

	if (!ResultFile)
	{
		cerr << "File could not be opened" << endl;
		exit(1);
	}
	ResultFile << "The number of trajectory pattern is : " << int2string(Miningspace->numberofP) << endl;
	ResultFile.close();
	cout << endl;

	cout << int2string(Miningspace->numberofP) << endl;

	// end of recording the total time
	finish = clock();
	cout << "number of candidates:" << Miningspace->candidates << endl;
	cout << "number of 1-pattern candidates:" << Miningspace->candidatesarry[0]<< endl;
	cout << "number of 2-pattern candidates:" << Miningspace->candidatesarry[1]<< endl;
	cout << "number of 3-pattern candidates:" << Miningspace->candidatesarry[2]<< endl;
	cout << "number of 4-pattern candidates:" << Miningspace->candidatesarry[3]<< endl;
	cout << "number of tuples scanned:"<< Miningspace->tuplesScanned << endl;
	totaltime = (double)(finish-start)/CLOCKS_PER_SEC;
	cout<< "Total time is " << totaltime << "s" <<endl;

//    getch();
	return 0;

}
